package com.cqs.leetcode.dp;

import com.cqs.leetcode.TestCaseUtils;

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * @author lixiaowen
 * @create 2019-12-20
 */
public class CoinChange322 {


    static class Solution {

        public int coinChange(int[] coins, int amount) {
            if (amount < 1) return 0;
            return coinChange(coins, amount, new int[amount]);
        }

        private int coinChange(int[] coins, int rem, int[] count) {
            if (rem < 0) return -1;
            if (rem == 0) return 0;
            if (count[rem - 1] != 0) return count[rem - 1];
            int min = Integer.MAX_VALUE;
            for (int coin : coins) {
                int res = coinChange(coins, rem - coin, count);
                if (res >= 0 && res < min)
                    min = 1 + res;
            }
            count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
            return count[rem - 1];
        }
    }


    public static void main(String[] args) {
        //int n = 1;
        CoinChange322 coin = new CoinChange322();
        int[] coins0 = {1, 2, 5};
        for (int i = 0; i < 0; i++) {
            System.out.println("面额 " + i + " coins:" + TestCaseUtils.arrFormat(coins0) + " 结果: " + coin.coinChange(coins0, i));
        }

        Map<int[], Integer> testCase = new HashMap<>();
        testCase.put(new int[]{186, 419, 83, 408}, 6249);
//        testCase.put(new int[]{3, 7}, 6249);
//        testCase.put(new int[]{186,419,83,408},61);
        Solution solution = new Solution();
        testCase.forEach((arr, amount) -> {
            int value = solution.coinChange(arr, amount);
//            value = coin.coinChange(arr, amount);
            System.out.println("面额 " + amount + " coins:" + TestCaseUtils.arrFormat(arr) + " 结果: " + value);
        });
    }

    /***
     * case 跑不通
     */
    static class Solution2 {
        /**
         * DP[N] = 1 + min{DP[N-coins[0],...., DP[N-coins[len-1]]}
         *
         * @param coins
         * @param amount
         * @return
         */
        public int coinChange(int[] coins, int amount) {
            if (amount < 0 || coins == null) return -1;
            if (coins.length == 1) {
                return amount % coins[0] == 0 ? amount / coins[0] : -1;
            }
            int[] DF = new int[amount + 1];
            for (int i = 1; i < DF.length; i++) {
                DF[i] = -1;
            }
            return coinChange(coins, amount, DF);
        }

        private int coinChange(int[] coins, int amount, int[] DP) {
            //终止条件
            if (amount <= 0) {
                return amount == 0 ? 0 : -1;
            }
            //使用缓存中间结果
            if (DP[amount] != -1) return DP[amount];
            Integer result = null;
            for (int i = 0; i < coins.length; i++) {
                int preSize = coinChange(coins, amount - coins[i], DP);
                //注意tmp== -1是无效的解，即不能通过DP[amount - coins[i]]组成
                if (preSize != -1) {
                    result = result == null ? preSize + 1 : Math.min(result, preSize + 1);
                }
            }
            //缓存
            DP[amount] = result == null ? -1 : result;
            return DP[amount];
        }

        public static void main(String[] args) {
            Solution2 coin = new Solution2();
            Map<int[], Integer> testCase = new LinkedHashMap<>();
            testCase.put(new int[]{1, 2, 5}, 6249);
            testCase.put(new int[]{3, 7}, 6249);
            testCase.put(new int[]{186, 419, 83, 408}, 3000);
            testCase.put(new int[]{186, 419, 83, 408}, 6249);
            testCase.forEach((arr, amount) -> {
                int value = coin.coinChange(arr, amount);
                System.out.println("面额 " + amount + " coins:" + arrFormate(arr) + " 结果: " + value);

            });
        }
        public static String arrFormate(int[] arr){
            if (arr == null || arr.length <= 0) return "";
            return Arrays.stream(arr).boxed().collect(Collectors.toList()).toString();
        }
    }

    /**
     * DP[N] = 1 + min{DP[N-coins[0],...., DP[N-coins[len-1]]}
     *
     * @param coins
     * @param amount
     * @return
     */
    public int coinChange(int[] coins, int amount) {
        if (amount < 0 || coins == null) return -1;
        if (coins.length == 1) {
            return amount % coins[0] == 0 ? amount / coins[0] : -1;
        }
        return coinChange(coins, amount, new int[amount + 1]);
    }

    private int coinChange(int[] coins, int amount, int[] DP) {
        //终止条件
        if (amount <= 0) {
            return amount == 0 ? 0 : -1;
        }
        //缓存中间结果
        if (DP[amount] != 0) return DP[amount];
        int result = -1;
        for (int i = 0; i < coins.length; i++) {
            int preSize = coinChange(coins, amount - coins[i], DP);
            //注意tmp== -1是无效的解，即不能通过DP[amount - coins[i]]组成
            if (preSize != -1 && (result == -1 || (1 + preSize) < result)) {
                result = preSize + 1;
            }
        }
        //缓存
        DP[amount] = result;
        return DP[amount];
    }
}
